/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM65 最长公共子序列(二)
 * https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&tqId=991075&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-04
 * Time: 16:13
 */

//string和sequence的区别是，sequence不要求连续，string要求连续,本题为sequence
//详解见：https://blog.csdn.net/hrn1216/article/details/51534607
import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        //检查特殊情况
        if (s1.isEmpty() || s2.isEmpty()) {
            return "-1";
        }
        int len1 = s1.length();
        int len2 = s2.length();
        //使用动态规划，我们以tmp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度
        //这里考虑到后续的计算，创建数组的时候应该预留出tmp[0][j],和tmp[i][0],并将它们赋值为0
        int[][] tmp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                //当s1和s2在此处的字符相等时
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    tmp[i][j] = 1 + tmp[i-1][j-1];
                } else {//当s1和s2在此处的字符不相等时
                    tmp[i][j] = Math.max(tmp[i - 1][j],tmp[i][j - 1]);
                }
            }
        }
        //检车最长公共子序列是否为空
        if (tmp[len1][len2] == 0) {
            return "-1";
        }
        //对动态规划好的数组进行分析,从右下角往左上角找子序列
        int cur = tmp[len1][len2];
        char[] lcs = new char[cur];
        int row = len1;
        int col = len2;
        while (cur > 0) {
            if (s1.charAt(row - 1) == s2.charAt(col - 1)) {//当s1和s2在此处的字符相同时
                lcs[cur - 1] = s1.charAt(row - 1);
                row--;
                col--;
                cur--;
            } else {      //当s1和s2在此处的字符不相同时
                if (tmp[row - 1][col] >= tmp[row][col - 1]) {
                    row--;
                } else {
                    col--;
                }
            }
        }
        return new String(lcs);
    }
}